class Solution:
    def maximumNumberOfOnes(self, width: int, height: int, length: int, max_ones: int) -> int:
        nums = []
        for i in range(length):
            for j in range(length):
                a1, b1 = divmod(width, length)
                a2, b2 = divmod(height, length)
                c1 = a1 + (1 if b1 > i else 0)
                c2 = a2 + (1 if b2 > j else 0)
                nums.append(c1 * c2)
        nums.sort(reverse=True)
        return sum(nums[:max_ones])


if __name__ == "__main__":
    # 4
    print(Solution().maximumNumberOfOnes(width=3, height=3, length=2, max_ones=1))

    # 6
    print(Solution().maximumNumberOfOnes(width=3, height=3, length=2, max_ones=2))

    # 测试用例95/105 : 42
    print(Solution().maximumNumberOfOnes(width=10, height=10, length=4, max_ones=5))
